/*
顺序表递增有序，设计算法在最少的时间内查找值为x的元素。
若找到，则将其于后继元素位置交换，否则按照递增顺序插入顺序表
*/
#include <iostream>
using namespace std;
#define maxsize 100

// 顺序表
typedef struct
{
  int data[maxsize];
  int length;
} Sqlist;

// 在顺序表中查找x
void search(Sqlist &L, int x)
{
  int low = 0, high = L.length - 1, mid, temp, i;
  
  // 遍历
  while (low <= high)
  {
    // 中间元素
    mid = (low + high) / 2;
    
    // 查找到x，
    if (L.data[mid] == x)
      break;
    
    // x在左半部分
    else if (L.data[mid] > x)
      high = mid - 1;
    
    // x在右半部分
    else
      low = mid + 1;
  }
  
  // x不在顺序表的末尾 -- x与后一个元素交换
  if (L.data[mid] == x && mid != L.length - 1)
  {
    temp = L.data[mid];
    L.data[mid] = L.data[mid + 1];
    L.data[mid + 1] = temp;
  }
  
  // 没找到x
  if (low > high)
  {
    // high后面的元素全部后移一位
    for (i = L.length - 1; i > high; --i)
      L.data[i + 1] = L.data[i];
    
    // 插入x
    L.data[i + 1] = x;
    
    // 更新长度
    L.length++;
  }
}

int main()
{
  // 定义顺序摆哦
  Sqlist A = {{2, 5, 9, 13, 19}, 5};
  
  // 查询元素6
  search(A, 6);
  
  // 打印
  for (int j = 0; j < A.length; ++j)
    cout << A.data[j] << endl;
}